package com.wang.transfer.util.algorithm;

import java.util.zip.CheckedInputStream;

/**
 * 斐波那契数列
 * 0 1 1 2 3 5 8 13 21 34 55
 */
public class Fib {

    public static void main(String[] args) {
//        System.out.println(calculate(10));
        System.out.println(calculate2(10));
    }


    public static int calculate(int num) {
        int[] arr = new int[num + 1];
        return reserve(arr, num);
    }

    // O(2 ^ n)
    private static int reserve(int[] arr, int num) {
        if (num == 0 || num == 1) {
            return num;
        }
        if (arr[num] != 0) {
            return arr[num];
        }
        arr[num] = reserve(arr, num - 1) + reserve(arr, num - 2);
        return arr[num];
    }

    // O(n)
    public static int calculate2(int num) {
        if (num == 0 || num == 1) {
            return num;
        }
        int low = 0, high = 1;
        int sum = 0;
        for (int i = 2; i <= num; i++){
            sum = low + high;
            low = high;
            high = sum;
        }
        return sum;
    }
}
